#pragma once

template<class K>
struct HashFunc//当是浮点数、有符号的负数、指针，此时取模都能完美的解决
{
	size_t operator()(const K& key)
	{
		return (size_t)key;//强制转换
	}
};

//模板特化（要有原模版才能特化）
template<>
struct HashFunc<string>//当是字符串时，返回数字能解决，取模的问题
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;//降低ASCII相加后的重复率
			hash += e;//ASCII码相加
		}
		return hash;
	}
};

namespace open_address//闭散列
{
	//查找时，遇到删除不能停
	enum State//存在 删除  的位置都可以继续查找
	{
		EXIST,//存在
		EMPTY,//空
		DELETE//删除
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;//数据
		State _state = EMPTY;//（开始是空）状态标识
	};

	template<class K, class V, class Hash = HashFunc<K>>//Hash传的是有符号的负数、指针、字符串时用传的缺省值，都能完美解决取模的问题
	class HashTable
	{
	public:
		//构造
		HashTable()
		{
			_tables.resize(10);//直接开10，间接保证了size和capacity是一样大的
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//不允许冗余
			{
				return false;
			}


			//扩容
			//if (_n / _tables.size() == 0.7)
			if (_n * 10 / _tables.size() >= 7)
			{
				//不能在这直接扩容（resize），因为当size变了，映射关系就变了
				//_tables.resize(_tables.size() * 2);

				//vector<HashData<K, V>> newTable(_tables.size() * 2);//扩容等于原来链表的2倍
				////遍历旧表，将所有数据映射到新表
				////...
				//_tables.swap(newTables);//这个方法会导致，原本旧表的，冲突也会带到新表里面，在新表里还得再走一次冲突

				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				{
					if (_tables[i]._state == EXIST)//旧表的对应位置，它的状态为存在，就放到新表里面去
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			//字符、指针不能取模（写一个能把字符、字符串、指针转为数字的模板，就能取模）
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();//找数据存储的位置（除以存有数据的长度，而不是capacity）
			while (_tables[hashi]._state == EXIST)//存在就++，去下一个位置找
			{
				++hashi;

				hashi %= _tables.size();//去下一个位置找
			}
			_tables[hashi]._kv = kv;//存值
			_tables[hashi]._state = EXIST;//改为存在状态
			++_n;//数据个数

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;

			//先算在这个表里的位置
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST//状态要为存在，不然查找时还能找出被删除 之前数据的地址
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//相等返回对应的地址
				}

				++hashi;//没有就++
				hashi %= _tables.size();//去表的下一个位置继续循环找
			}

			return nullptr;//没有返回空
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);//直接进行查找
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;//直接改状态，不用抹除
				return true;
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//表中存储数据的个数（声明）
	};

	//不需要写析构函数
	//它有自定义类型（会调用自己的析构,_tables会自己释放掉）（会调用深拷贝）和内置类型（会调用浅拷贝）

	void testHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 11,21,4,14,24,15,9 };
		for (auto e : a)
		{
			ht.Insert({ e,e });
		}

		ht.Insert({ 19,19 });
		ht.Insert({ 19,191 });
		ht.Insert({ 19,190 });

		cout << ht.Find(24) << endl;
		ht.Erase(4);
		cout << ht.Find(24) << endl;
		cout << ht.Find(4) << endl;
	}

	struct StringHashFunc//支持把string转成整型
	{//支持字符串取模
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto e : s)
			{
				hash *= 31;
				hash += e;//ASCII码相加
			}
			return hash;
		}
	};

	void TestHT2()
	{
		//两层映射
		//string -> size_t -> n
		HashTable<string, string, StringHashFunc> ht;
		ht.Insert({ "sort","排序" });//字符不能取模
		ht.Insert({ "left","左边" });

		cout << StringHashFunc()("bacd") << endl;
		cout << StringHashFunc()("abcd") << endl;
		cout << StringHashFunc()("aadd") << endl;
	}
}


namespace hash_bucket//开散列
{
	 template<class K,class V>
	 struct HashNode
	 {
		 pair<K, V> _kv;
		 HashNode<K, V>* _next;

		 HashNode(const pair<K,V>& kv)
			 :_kv(kv)
			 ,_next(nullptr)
		 {}
	 };

	 template<class K,class V, class Hash = HashFunc<K>>
	 class HashTable
	 {
		 typedef HashNode<K, V> Node;
	 public:
		 //构造
		 HashTable()
		 {
			 _tables.resize(10, nullptr);
		 }

		 //要写析构，vector释放的时候，不会释放桶里面（挂在下面的链表）的数据（内置类型），指针不会调用析构函数
		 ~HashTable()
		 {
			 //依次把每个桶释放
			 for (size_t i = 0; i < _tables.size(); i++)
			 {
				 Node* cur = _tables[i];
				 while (cur)
				 {
					 Node* next = cur->_next;//先保存下一个数据
					 delete cur;//再释放
					 cur = next;
				 }
				 _tables[i] = nullptr;
			 }
		 }


		 bool Insert(const pair<K, V>& kv)
		 {
			 Hash hs;
			 size_t hashi = hs(kv.first) % _tables.size();//取模算出hashi对应的位置出来

			 //控制负载因子
			 //负载因子==1 扩容
			 //负载因子越低，空间效率越低，时间效率越高
			 //负载因子越高，空间效率越高，时间效率越低
			 if (_n == _tables.size())//负载因子到1，进行扩容
			 {
				 //新开结点
				 /*HashTable<K, V> newHT;
				 newHT._tables.resize(_tables.size() * 2);
				 for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				 {
					 Node* cur = _tables[i];
					 while (cur)//遍历桶
					 {
						 newHT.Insert(cur->_kv);//把所以旧表的数据，插入到新表里面
						 cur = cur->_next;
					 }
				 }
				 _tables.swap(newHT._tables);//新表和旧表进行交换*/

				 //直接挪动结点
				 vector<Node*> newtables(_tables.size() * 2, nullptr);
				 for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				 {
					 Node* cur = _tables[i];
					 while (cur)//遍历桶
					 {
						 //提前保存下一个结点，不然下次找不到
						 Node* next = cur->_next;

						//直接把旧表中的结点，挪到新表重新映射的位置
						 size_t hashi = hs(cur->_kv.first) % newtables.size();//在新表找到对应的位置
						 //头插到新表
						 cur->_next = newtables[hashi];//我先指向桶的第一个
						 newtables[hashi] = cur;//把桶的第一个给我

						 cur = next;
					 }
					 _tables[i] = nullptr;//桶的最后一个指向空
				 }
				 _tables.swap(newtables);
			 }

			 //头插
			 Node* newnode = new Node(kv);
			 //找到位置，进行头插
			 newnode->_next = _tables[hashi];//（第一个的地址在表里面）表里面指向桶里的第一个
			 _tables[hashi] = newnode;//把桶里面的第一个给newnode（在桶里面头插）
			 ++_n;

			 return true;
		 }

		 Node* Find(const K& key)
		 {
			 Hash hs;
			 size_t hashi = hs(key) % _tables.size();//先算在表里面的位置
			 Node* cur = _tables[hashi];
			 while (cur)
			 {
				 if (cur->_kv.first == key)
				 {
					 return cur;
				 }
				 cur = cur->_next;
			 }
			 return nullptr;
		 }

		 bool Erase(const K& key)
		 {
			 size_t hashi = key % _tables.size();
			 Node* prev = nullptr;
			 Node* cur = _tables[hashi];
			 while (cur)
			 {
				 if (cur->_kv.first == key)
				 {
					 //有这个结点，进行删除，分情况进行讨论
					 if (prev == nullptr)
					 {
						 //没有前一个，直接指向下一个
						 _tables[hashi] = cur->_next;
					 }
					 else
					 {
						 //有前一个，就让前一个的next指向我的后一个
						 prev->_next = cur->_next;
					 }
					 delete cur; 
					 --_n;
					 return true;
				 }
				 prev = cur;
				 cur = cur->_next;
			 }
			 return false;
		 }

	 private:
		 //vector<list<pair<K, V>>> _tables;//指针数组

		 vector<Node*> _tables;//本质是一个指针数组
		 size_t _n = 0;//表中存储的数据个数数据
	 };

	 void TestHT1()
	 {
		 HashTable<int, int> ht;
		 int a[] = { 11,21,4,14,24,15,9,19,29,39,49 };
		 for (auto e : a)
		 {
			 ht.Insert({ e,e });
		 }

		 ht.Insert({ -6,6 });

		 for (auto e : a)
		 {
			 ht.Erase(e);
		 }
	 }

	 void TestHT2()
	 {
		 HashTable<string, string> ht;
		 ht.Insert({ "sort", "排序" });
		 ht.Insert({ "left", "左边" });
	 }
}